GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Gift-Wrapping-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Gift-Wrapping-Algorithmus</h1>

</header>

</div>

Der Gift-Wrapping-Algorithmus, auch Jarvis-March genannt, ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a> zur Berechnung der <a href="Konvexe_H%C3%BClle" title="Konvexe Hülle">konvexen Hülle</a> einer Punktemenge im zweidimensionalen Raum. Er wurde 1973 von R. A. Jarvis veröffentlicht. Der Algorithmus gehört zu den „<a href="Ausgabesensitiver_Algorithmus" title="Ausgabesensitiver Algorithmus">ausgabesensitiven</a>“ (englisch output-sensitive) Algorithmen.

<div class="mw-heading mw-heading2"><h2 id="Beschreibung">Beschreibung</h2></div>

Gegeben sei eine Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S=\{s_{1},\dotsc ,s_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S=\{s_{1},\dotsc ,s_{n}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de7198cbdf6e6e61b4765ab759f4cb9d5021086f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.554ex; height:2.843ex;" alt="{\displaystyle S=\{s_{1},\dotsc ,s_{n}\}}" loading="lazy"> von Punkten in einer Ebene. Als Startpunkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> wird der Punkt mit der kleinsten <a href="Ordinate" class="mw-redirect" title="Ordinate">Ordinate</a> gewählt. Sind dies mehrere, so wird aus diesen der Punkt mit der kleinsten <a href="Abszisse" class="mw-redirect" title="Abszisse">Abszisse</a> gewählt. Der Startpunkt ist somit Teil der konvexen Hülle. Nun wird ein beliebiger Punkt aus der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> gewählt, mit welchem der Startpunkt eine <a href="Gerade" title="Gerade">Gerade</a> bildet. Als Nächstes werden die restlichen Punkte aus der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> überprüft, ob ein Punkt links dieser Geraden liegt. Rechts und links ergeben sich in diesem Zusammenhang aus dem Winkel zwischen dem Richtungsvektor der Trennungsgeraden und dem Vektor definiert durch den Anfangspunkt der Geraden und den zu überprüfenden Punkt. Ist dieser Winkel kleiner als 180°, dann wird der Punkt als rechts von der Geraden betrachtet, bei Winkeln größer 180° als links von ihr. Wird ein Punkt links der Geraden gefunden, bildet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> mit diesem eine neue Gerade. Anschließend wird der Rest der Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> überprüft. Für jeden Punkt, der links von dieser Geraden liegt, wird dieser Vorgang wiederholt. Wurden alle Punkte überprüft, ist der zuletzt gefundene Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/398f438d75434e6fbf48dc232c1ad7228a738568.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{1}}" loading="lazy"> der nächste Punkt auf der konvexen Hülle. Nun wird <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/398f438d75434e6fbf48dc232c1ad7228a738568.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{1}}" loading="lazy"> als neuer Startpunkt gewählt und der gesamte Vorgang wiederholt, bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/671bd891701e0d6cfa6da0114a5dd64233b58709.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{0}}" loading="lazy"> wieder der Startpunkt ist.

Für jeden Punkt auf der konvexen Hülle muss die komplette Menge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> durchlaufen werden. Dieser Teil wird in einer Schleife ausgeführt, wobei jeder Schleifendurchlauf eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"> besitzt. Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> die Anzahl der Punkte auf der konvexen Hülle, ergibt sich eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(nh)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(nh)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ebf6649527d3721b66d4d5eb1bbc7fafcc992e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.393ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(nh)}" loading="lazy">. Im <a href="Worst_Case" title="Worst Case">Worst Case</a>, wenn alle Punkte auf der konvexen Hülle liegen, ergibt sich somit eine Laufzeit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy">. Da der Algorithmus von der Anzahl der Punkte auf der konvexen Hülle abhängt, gehört er zu den sogenannten ausgabesensitiven Algorithmen.

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<pre> jarvis(P)

startpunkt = Punkt mit kleinster Ordinate

convexhull = new()

wiederhole

convexhull.add(startpunkt)

endpunkt = P[0]

wenn startpunkt == endpunkt

endpunkt = P[1]

für i von 1 bis |P|

ist (endpunkt == startpunkt) oder (P[i] links von der Geraden zwischen startpunkt und endpunkt)

endpunkt = P[i]

startpunkt = endpunkt

bis endpunkt == convexhull[0]

</pre>

<div class="mw-heading mw-heading2"><h2 id="Programmierung">Programmierung</h2></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C-Sharp" title="C-Sharp">C#</a> zeigt die Implementierung des Gift-Wrapping-Algorithmus. Die Punkte und die <a href="Konvexe_H%C3%BClle" title="Konvexe Hülle">konvexe Hülle</a> werden auf dem Hauptfenster gezeichnet. Das Programm verwendet mehrere <a href="Klasse_(Objektorientierung)" title="Klasse (Objektorientierung)">Klassen</a>. Die <a href="Methode_(Programmierung)" title="Methode (Programmierung)">Methoden</a> für den eigentlichen Algorithmus werden in der Klasse GiftWrapping deklariert.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

<td style="text-align:left; font-size: 95%;">Code-Schnipsel

</td></tr>

<tr>

<td>

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr" dir="ltr"><pre>using System;

using System.Collections.Generic;

using System.Drawing;

using System.Windows.Forms;

public class GiftWrapping

{

// Diese Methode bestimmt die Orientierung des drei Punkte. Wenn die Punkte im Uhrzeigersinn sind, wird ein Wert größer als 0 zurückgegeben. Wenn die Punkte im Gegenuhrzeigersinn sind, wird ein Wert kleiner als 0 zurückgegeben. Wenn die Punkte kollinear sind, wird der Wert 0 zurückgegeben.

public int GetOrientation(Point point1, Point point2, Point point3)

{

return (point2.Y - point1.Y) * (point3.X - point2.X) - (point2.X - point1.X) * (point3.Y - point2.Y);

}

// Diese Methode gibt eine Liste der Punkte der konvexen Hülle zurück

public List<Point> GetConvexHull(List<Point> points)

{

List<Point> convexHull = new List<Point>();

int numberOfpoints = points.Count;

if (numberOfpoints < 3) // Wenn weniger als 3 Punkte vorhanden sind, wird eine leere Liste zurückgegeben

{

return convexHull;

}

float minimumX = points[0].X;

int indexOfMinimum = 0;

// Diese for-Schleife durchläuft die verbleibenden Punkte und ermittelt den Punkt ganz links und bei Gleichheit den untersten Punkt

for (int i = 1; i < numberOfpoints; i++)

{

float x = points[i].X;

if (x < minimumX || minimumX == x && points[i].Y < points[indexOfMinimum].Y)

{

minimumX = points[i].X;

indexOfMinimum = i;

}

int currentIndex = indexOfMinimum;

int nextIndex;

// Diese do-while-Schleife beginnt beim Punkt ganz links und läuft im Gegenuhrzeigersinn, bis sie wieder den Anfangspunkt erreicht. Die Anzahl der Durchläufe der Schleife ist die Anzahl der Punkte der konvexen Hülle.

do

{

convexHull.Add(points[currentIndex]); // Fügt den aktuellen Punkt der Liste der Punkte der konvexen Hülle hinzu

nextIndex = (currentIndex + 1) % numberOfpoints; // Erhöht den Index nextIndex um 1 und setzt ihn zurück auf 0, wenn der maximale Wert überschritten ist

// Diese for-Schleife durchläuft alle Punkte und sucht einen Punkt mit Index nextIndex, sodass die Punkte mit den Indexen currentIndex, nextIndex, x für alle Indexe x im Gegenuhrzeigersinn sind

for (int i = 0; i < numberOfpoints; i++)

{

if (GetOrientation(points[currentIndex], points[nextIndex], points[i]) < 0) // Wenn der Punkt mit Index i weiter im Gegenuhrzeigersinn liegt als der Punkt mit Index nextIndex, wird nextIndex aktualisiert

{

nextIndex = i;

}

// Der Punkt mit Index nextIndex ist der Punkt, der in Bezug auf den Punkt mit Index currentIndex am weitesten im Gegenuhrzeigersinn liegt. Nach der folgenden Zuweisung wird dieser Punkt der konvexen Hülle hinzugefügt.

currentIndex = nextIndex;

}

while (currentIndex != indexOfMinimum); // While we don't come to first

return convexHull;

}

}

// Klasse für das Hauptfenster

public partial class MainForm : Form

{

private Graphics graphics;

private List<Point> points = new List<Point>(); // Liste der Punkte

private List<Point> convexHull = new List<Point>(); // Liste der Punkte der konvexen Hülle

private double x1, y1, x2, y2;

public MainForm()

{

x1 = 100; y1 = 100; x2 = 700; y2 = 700; // Setzt die Koordinaten der Eckpunkte der quadratischen Zeichenfläche

Random random = new Random(); // Initialisiert den Zufallsgenerator

int numberOfPoints = 100;

for (int i = 0; i < numberOfPoints; i++) // Diese for-Schleife erzeugt 100 zufällige Punkte innerhalb der quadratischen Zeichenfläche

{

Point point = new Point();

point.X = (int)(random.NextDouble() * (x2 - x1) + x1);

point.Y = (int)(random.NextDouble() * (y2 - y1) + y1);

points.Add(point); // Fügt den Punkt der Liste hinzu

}

GiftWrapping giftWrapping = new GiftWrapping(); // Erzeugt ein Objekt der Klasse GiftWrapping

convexHull = giftWrapping.GetConvexHull(points); // Aufruf der Methode, die die konvexe Hülle zurückgibt

InitializeComponent();

Text = "Konvexe Hülle";

Width = 800;

Height = 800;

graphics = CreateGraphics(); // Erzeugt ein Grafikobjekt für das Zeichnen auf dem Hauptfenster.

Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.

}

// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird.

private void OnPaint(object sender, PaintEventArgs e)

{

for (int i = 0; i < points.Count; i++)

{

graphics.FillRectangle(new SolidBrush(Color.FromArgb(0, 0, 0)), points[i].X - 1, points[i].Y - 1, 2, 2); // Zeichnet die Punkte

}

int numberOfPoints = convexHull.Count;

for (int i = 0; i < numberOfPoints; i++)

{

graphics.DrawLine(new Pen(Color.FromArgb(0, 0, 255)), convexHull[i], convexHull[(i + 1) % numberOfPoints]); // Zeichnet die Kanten der konvexen Hülle

}

}

</pre></div>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Jarvis, R. A.: <cite style="font-style:italic">On the identification of the convex hull of a finite set of points in the plane</cite>. In: <cite style="font-style:italic">Information Processing Letters</cite>. 2. Jahrgang, 1973, S. 18–21, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016/0020-0190%2873%2990020-3">10.1016/0020-0190(73)90020-3</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Gift-Wrapping-Algorithmus&rft.atitle=On+the+identification+of+the+convex+hull+of+a+finite+set+of+points+in+the+plane&rft.au=Jarvis%2C+R.+A.&rft.btitle=Information+Processing+Letters&rft.date=1973&rft.doi=10.1016%2F0020-0190%2873%2990020-3&rft.genre=book&rft.pages=18-21&rft.volume=2.+Jahrgang" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.iti.fh-flensburg.de/lang/algorithmen/geo/jarvis.htm">Erklärung und Pseudocode</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> OpenGenus IQ: <a rel="nofollow" class="external text" href="https://iq.opengenus.org/gift-wrap-jarvis-march-algorithm-convex-hull/">Gift Wrap Algorithm (Jarvis March Algorithm) to find Convex Hull</a>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/">Convex Hull</a>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-02-18" href="https://de.wikipedia.org/wiki/?title=Gift-Wrapping-Algorithmus&oldid=242309995">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>